package myjava.algorithm.leetcode;

import java.util.*;

public class WordLadder3 {

	static List<List<String>> findLadders(String start, String end,
			Set<String> dict) {
		List<List<String>> res = new ArrayList<List<String>>();
		if (canTransform(start, end)) {
			List<String> path = new ArrayList<String>();
			path.add(start);
			path.add(end);
			res.add(path);
			return res;
		}
		List<String> bfs = new ArrayList<String>();
		int level = 1;
		int begin = 0;
		/*
		 * a HashMap could be both 1) track explored and 2) length calculate but
		 * we alread have `Set<String> dict` to track the explored
		 */
		HashMap<String, Integer> explored = new HashMap<String, Integer>();
		bfs.add(start);
		explored.put(start, 0);
		dict.remove(start);
		dict.remove(end);
		List<List<String>> levels = new ArrayList<List<String>>();
		int minLength = -1;
		outer: while (begin < bfs.size()) {
			if (minLength >= 0) { // !!!
				break;
			}
			int tail = bfs.size();
			// add new level list
			if (levels.size() == level - 1) {
				levels.add(new ArrayList<String>());
			}
			for (int i = begin; i < tail; i++) {
				String curr = bfs.get(i); // get(i)
				for (int j = 0; j < curr.length(); j++) {
					for (char c = 'a'; c <= 'z'; c++) {
						String s = changeChar(curr, j, c);
						// !!! dict Set MAY NOT include "start & end"
						if (s.equals(end)) { // !!! FOUND min path
							explored.put(end, level);
							minLength = level + 1;
							levels.get(level - 1).add(end);
							break outer;
						}
						if (dict.contains(s) && !explored.containsKey(s)) {
							explored.put(s, level);
							dict.remove(s);
							bfs.add(s);
							// add s into its level
							levels.get(level - 1).add(s);
						}
					} // end of inner for
				}
			} // end of outer for each level
			level++;
			begin = tail;
		} // end of while
		if (minLength == -1) {
			return res;
		}
		/* DFS DP */
		HashMap<String, List<List<String>>> cache = new HashMap<String, List<List<String>>>();
		return dfsPathDP(levels, 0, start, end, cache);
	}

	static List<List<String>> dfsPathDP(List<List<String>> levels, int level,
			String start, String end, HashMap<String, List<List<String>>> cache) {
		if (cache.containsKey(start)) {
			return cache.get(start);
		}
		if (level == levels.size()) {
			if (start.equals(end)) {
				List<String> pathEnd = new ArrayList<String>();
				pathEnd.add(end);
				List<List<String>> endRes = new ArrayList<List<String>>();
				endRes.add(pathEnd);
				cache.put(start, endRes);
				return cache.get(start);
			} else {
				return null;
			}
		}
		List<List<String>> res = new ArrayList<List<String>>();
		List<String> currLevel = levels.get(level);
		for (String s : currLevel) {
			if (!canTransform(start, s)) {
				continue;
			}
			List<List<String>> tailingRes = dfsPathDP(levels, level + 1, s,
					end, cache);
			if (tailingRes == null) { // !!!
				continue;
			}
			for (List<String> path : tailingRes) {
				List<String> newPath = new ArrayList<String>();
				newPath.add(start);
				newPath.addAll(path);
				res.add(newPath);
			}
		} // end outer for
		cache.put(start, res);
		return res;
	}

	static String changeChar(String s, int i, char c) {
		StringBuilder sb = new StringBuilder(s);
		sb.setCharAt(i, c);
		return sb.toString();
	}

	static boolean canTransform(String s1, String s2) {
		/* a very simple version cause string is determined in length */
		int diff = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) != s2.charAt(i)) {
				if (diff == 0) {
					diff++;
					;
				} else {
					return false;
				}
			}
		}
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// TODO Auto-generated method stub
		Set<String> dict = new HashSet<String>();
		dict.add("hot");
		dict.add("dot");
		dict.add("dog");
		dict.add("lot");
		// dict.add("lom");
		// dict.add("lim");
		// dict.add("lok");
		dict.add("log");

		dict.add("a");
		dict.add("b");
		dict.add("c");

		WordLadder3 w = new WordLadder3();

		System.out.println(w.findLadders("hit", "cog", dict));
	}

}
